#include <iostream>
#include <string>
using namespace std;

const int N = 1e5 + 5;

int h[N], hp[N], ph[N], n, idx;

void h_swap(int a, int b)
{
    swap(ph[hp[a]], ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}

void adjust_down(int p)
{
    int c = p * 2 + 1;
    while(c < n)
    {
        if(c + 1 < n && h[c + 1] < h[c]) c++;
        if(h[c] < h[p]) h_swap(c, p);
        else break;
        p = c;
        c = p * 2 + 1;
    }
}

void adjust_up(int c)
{
    while(c)
    {
        int p = (c - 1) / 2;
        if(h[c] < h[p]) h_swap(c, p);
        else break;
        c = p;
    }
}

int main()
{
    int t, k, x; cin >> t;
    while(t--)
    {
        string str; cin >> str;
        if(str == "I") {
            cin >> x;
            h[n] = x;
            ph[idx] = n;
            hp[n] = idx;
            adjust_up(n);
            n++, idx++;
        } else if(str == "PM") {
            cout << h[0] << endl;
        } else if(str == "DM") {
            h_swap(0, --n);
            adjust_down(0);
        } else if(str == "D") {
            // cin >> k; k--;
            // h_swap(ph[k], --n); // 这一步会改变ph[k],导致下一步出错
            // adjust_down(ph[k]), adjust_up(ph[k]);
            cin >> k; k = ph[k - 1];
            h_swap(k, --n);
            adjust_down(k), adjust_up(k);
        } else {
            cin >> k >> x; k = ph[k - 1];
            h[k] = x;
            adjust_down(k), adjust_up(k);
        }
    }
    return 0;
}